/*
这是一个通用的二叉搜索树实现
*/

#include "bst_tree.h"
#include <stdlib.h>
#include <string.h>

// bst 树节点
struct node_t {
  bst_node left;
  bst_node right;
  size_t size; // 数组数据大小
  char data[]; // 数据本身
};

// bst 树
struct bst_t {
  bst_node root;
  cmp_func_t *func_cmp;
  get_key_func_t *func_get_key;
};

static void *_search(btree bst, const bst_node node, const void *key);

static bool _insert(btree bst, bst_node *pnode, const void *data, size_t size);

static bool _delete(btree bst, bst_node *pnode, const void *key);

static void _clear(bst_node node);

static bst_node detach_min(bst_node *pnode);

static int _in_order(bst_node node, bool (*action)(void *data));

static int _pre_order(bst_node node, bool (*action)(void *data));

static int _post_order(bst_node node, bool (*action)(void *data));

const void *default_get_key(const void *data) { return data; }

/* 创建二叉树 */
btree bst_create(cmp_func_t *cmp, get_key_func_t *getKey) {
  btree bst = NULL;

  if (cmp != NULL)
    bst = malloc(sizeof(struct bst_t));

  if (bst != NULL) {
    bst->root = NULL;
    bst->func_cmp = cmp;
    bst->func_get_key = (getKey != NULL) ? getKey : default_get_key;
  }

  return bst;
}

/* 向二叉树中插入数据 */
bool bst_insert(btree bst, const void *data, size_t size) {
  if (bst == NULL || data == NULL || size == 0)
    return false;
  return _insert(bst, &(bst->root), data, size);
}

/* 在二叉树找查找 */
const void *bst_search(btree bst, const void *key) {
  if (bst == NULL || key == NULL)
    return false;

  return _search(bst, bst->root, key);
}

/* 删除二叉树中的指定数据 */
bool bst_delete(btree bst, const void *key) {
  if (bst == NULL || key == NULL)
    return false;

  return _delete(bst, &(bst->root), key);
}

/* 清空树节点,保留tree对象 */
void bst_clear(btree bst) {
  if (bst != NULL) {
    _clear(bst->root);
    bst->root = NULL;
  }
}

/* 清空树节点,释放tree对象 */
void bst_destory(btree bst) {
  if (bst != NULL) {
    bst_clear(bst);
    free(bst);
  }
}

// 中序遍历 LNR 从小到大
int bst_in_order(btree bst, bool (*action)(void *data)) {
  if (bst == NULL || action == NULL)
    return 0;

  return _in_order(bst->root, action);
}

// 前序遍历 NLR
int bst_pre_order(btree bst, bool (*action)(void *data)) {
  if (bst == NULL || action == NULL)
    return 0;

  return _pre_order(bst->root, action);
}

// 后序遍历 LRN
int bst_post_order(btree bst, bool (*action)(void *data)) {
  if (bst == NULL || action == NULL)
    return 0;

  return _post_order(bst->root, action);
}

//--------------------------------------------------------------------------

/*
 内部私有递归函数, 辅助bst_search查找,该函数会根据data遍历左子树或者右子树

 bst : struct node_t 结构指针
 node: struct node_t 指针, 在node的子树中查找.

 data: 被查找数据的起始地址
*/
static void *_search(btree bst, const bst_node node, const void *key) {
  if (node == NULL)
    return NULL;

  int cmp_res = bst->func_cmp(key, bst->func_get_key(node->data));
  if (cmp_res < 0) // 左子树中递归查找, 因为左子树都是小于node的数据
    return _search(bst, node->left, key);
  else if (cmp_res > 0) // 右子树中递归查找
    return _search(bst, node->right, key);
  else
    return node->data;
}

/*
 内部私有递归函数, 辅助bst_insert插入,该函数会中序遍历创建二叉树

 bst : struct node_t 结构指针
 pnode: struct node_t 的二级指针, 传入NULL时,插入新节点, pnode非空时,
         在pnode的子树中查找.
 data: 插入的数据的起始地址
 size: 数据的大小

*/
static bool _insert(btree bst, bst_node *pnode, const void *data, size_t size) {
  bst_node p = *pnode;

  if (p == NULL) { // 新节点
    if ((p = malloc(sizeof(struct node_t) + size)) != NULL) {
      p->left = p->right = NULL;   // 初始化成员
      memcpy(p->data, data, size); // 填充数据
      p->size = size;
      *pnode = p; // 插入新创建的节点
      return true;
    } else
      return false;
  } else {
    const void *key1 = bst->func_get_key(data);
    const void *key2 = bst->func_get_key(p->data);
    if (bst->func_cmp(key1, key2) < 0)
      return _insert(bst, &(p->left), data, size); // 递归左子树直到可以插入
    else
      return _insert(bst, &(p->right), data, size); // 递归左子树直到可以插入
  }
}

/*
这是一个删除辅助函数, 以将要被删除的节点n作为根节点,该函数会找到它的右子树中
最小值节点m,然后使用m的右子树替换m,并将m节点返回
*/
static bst_node detach_min(bst_node *pnode) {
  bst_node node = *pnode;
  if (node == NULL)
    return NULL;
  else if (node->left != NULL)
    return detach_min(&(node->left)); // 递归完左子树
  else {                              // node 节点是最小值
    *pnode = node->right; // 将这个最小节点用它的右子树替换
    return node;          //返回最小节点
  }
}

/*
  删除辅助函数
*/
static bool _delete(btree bst, bst_node *pnode, const void *key) {
  bst_node node = *pnode;
  if (node == NULL)
    return false;

  int cmp_res = bst->func_cmp(key, bst->func_get_key(node->data));

  if (cmp_res < 0) // 递归左子树查找
    return _delete(bst, &(node->left), key);
  else if (cmp_res > 0) // 递归右子树查找
    return _delete(bst, &(node->right), key);
  else {                    // cmp_res == 0 找到将要被删除的节点
    if (node->left == NULL) // 只有右节点,或者是叶子节点无分支
      *pnode = node->right; // 右子树直接提升一层
    else if (node->right == NULL) // 只有左节点或者是叶子节点无分支
      *pnode = node->left;        // 左子树直接提升一层
    else {                        // 该节点下有2条分支
      bst_node pmin = detach_min(&(node->right)); // node 指向将被删除的节点
      *pnode = pmin;                              // 用最小节点替换
      pmin->left = node->left;                    //修复左分支
      pmin->right = node->right;                  //修复右分支
    }
    free(node);
    return true;
  }
}

/*
递归释放节点
*/
static void _clear(bst_node node) {
  if (node != NULL) {
    _clear(node->left);
    _clear(node->right);
    free(node);
  }
}

// LNR
static int _in_order(bst_node node, bool (*action)(void *data)) {
  int count = 0;
  if (node == NULL)
    return 0;

  count = _in_order(node->left, action);
  // root 节点
  if (action(node->data))
    ++count;

  count += _in_order(node->right, action);
  return count;
}

// NLR
static int _pre_order(bst_node node, bool (*action)(void *data)) {
  int count = 0;
  if (node == NULL)
    return 0;

  if (action(node->data))
    ++count;

  count = _pre_order(node->left, action);
  count += _pre_order(node->right, action);
  return count;
}

// LRN
static int _post_order(bst_node node, bool (*action)(void *data)) {
  int count = 0;
  if (node == NULL)
    return 0;

  count = _post_order(node->left, action);
  count += _post_order(node->right, action);

  if (action(node->data))
    ++count;

  return count;
}